프로세스 스케줄러

어떤 프로세스 얼마나 오랫동안 실행할지 결정
실행 중인 시스템 프로세스에 프로세서 동작 시간이라는 유한한 자원 분배
리눅스 같은 멀티태스킹 OS의 기본 요소
실행 프로세스 선택 과정을 통해, 시스템 최대 사용률 끌어내야 하고,
사용자에게 여러 개의 프로세스가 동시에 실행되는 느낌을 줘야 함

원리는 간단
실행 가능한 프로세스가 있다면, 그 중 어떤 것이던 실행되야 함
프로세서 개수보다 프로세스의 개수가 많다면 특정 순간에 일부 프로세스는 실행 중 아니게 됨
이 경우 실행되기를 기다림
스케줄러가 해결할 근본적 문제는 실행 가능한 프로세스 여러 개가 있을 때 어떤 프로세스를 다음에 실행할 것인가 결정하는 것

멀티태스킹

멀티태스킹 OS : 하나 이상의 프로세스를 동시에 중첩 형태로 실행할 수 있는 OS

멀티태스킹을 통해 프로세서 하나인 시스템에서도 여러 개의 프로세스를 동시 실행하는 느낌 줄 수 있음
프로세서가 여러 개면 실제로 여러 프로세스 동시 실행 가능

많은 프로세스 대기 상태 혹은 잠든 상태 될 수 있음(이 경우 메모리상에는 있지만 실행 가능한 상태 아님)
커널은 이런 프로세스를 특정 조건(인터럽트) 발생전까지 대기 상태로 둠

메모리상엔 많은 프로세스 있을 수 있지만 현대 리눅스 시스템에서 실행 중인 프로세스는 하나뿐

• 멀티태스킹 운영체제

  • 협동형 멀티태스킹cooperative multitasking
  • 선점형 멀티태스킹preemptive multitasking : 프로세스 실행을 언제 중단하고 다른 프로세스 실행할지 스케줄러가 결정하는데 실행 중인 프로세스 강제 중지하는 작업을 선점preemption이라 함, 리눅스도 이것 지원함

선점형 멀티태스킹preemptive multitasking

프로세스가 선점되기 전까지 프로세스에 주어지는 시간 보통 미리 정해지고 프로세스의 타임슬라이스timeslice라고 함
타임슬라이스 관리하는 방식으로 전체적인 시스템 스케줄링 결정
한 프로세스가 프로세서 독점 방지

요즘 OS 시스템 정책과 프로세스 동작 관련 함수 이용 동적으로 타임슬라이스 계산

리눅스 특유 '공정fair' 스케줄러는 타임슬라이스 값을 그 자체로 적용 안하는 방식으로 동작

대부분 OS 선점형 멀티태스킹 지원 유닉스는 태초부터 선점형 멀티태스킹 지원

협동형 멀티태스킹cooperative multitasking

프로세스가 자발적으로 실행 중단 안하면 한 프로세스 중지 불가능
프로세스가 자발적으로 동작 중단하는 행동을 양보yield라고 함
이상적으로 프로세스가 자주 양보해서 실행 중인 프로세스가 충분한 프로세서 동작 시간 확보 가능하지만 OS가 이것을 강제 불가함
스케줄러가 실행 시간에 관해 전체적 결정 불가함
사용자 의도보다 더 오래 독점할 가능성 있음
양보하지 않는 큰 프로세스가 전체 시스템 먹통 만들 수 있음

Mac OS 9, 윈도우 3.1과 이것들의 이전버전이 해당됨

리눅스의 프로세스 스케줄러

2.5 커널에 도입된 O(1) 스케줄러 : 상수 시간 알고리즘 사용, 프로세서마다 별도의 실행 대기열queue 사용으로 이전 스케줄러의 설계상 제약 제거함

잘 동작하다 이후 문제 발견됨
커다란 서버 작업에는 이상적이나
응답시간에 민감한 애플리케이션인 대화형interactive 프로세스가 중요한 데스크톱 시스템에서 평균 이하 성능 보임

2.6 커널에 도입된 새로운 프로세스 스케줄러 회전 계단식 기한Rotating Staircase Deadline 스케줄러 : 공정 스케줄링 개념을 큐잉 이론에서 빌려 적용함
위로부터 영감을 받아 2.6.23 커널부터 CFS라고 부르는 완전 공정 스케줄러가 O(1) 스케줄러 대신하게 됨

정책

정책Policy는 스케줄러가 무엇을 언제 실행할 것인지를 정하는 동작을 말함
스케줄러의 정책을 통해 시스템의 전체적인 느낌 정해지는 경향
프로세서 시간의 사용을 최적화하는 책임이 있어 매우 중요함

입출력중심 프로세스와 프로세서중심 프로세스

• 프로세스를 두 가지로 분류 가능

  • 입출력중심 프로세스 : 입출력 요청 후 기다리는데 대부분 시간 사용, 실제 실행시간 매우 짧음, (디스크, 키보드, 네트워크 등 대기 상태 발생 가능한 모든 시스템 자원의 입출력 대상)
  • 프로세서중심 프로세스 : 대부분의 시간 코드 실행에 사용, 보통 선점될때까지 계속 실행됨, 이런 프로세스 자주 실행할수록 시스템 반응 나빠짐, 좀 더 긴시간 덜 자주 실행하는게 좋음, 많은 양 수학적 계산 실행하는 ssh-keygen, MATLAB이 예시 위 분류는 상호배타적이지는 않음
    동시에 두 가지 특성 가질 수 있음 (e.g. X 윈도우 서버, 워드 프로세서)

시스템의 스케줄링 정책은 상충되는 두 가지 목적 달성하고자 함
프로세스 응답시간(지연시간) 빠르게, 시스템 사용률 최대화(산출물throughput 극대화)

유닉스 시스템 스케줄러 정책은 입출력중심 프로세스에 관대한 경향 => 빠른 프로세스 응답시간
리눅스도 대화형 작업에 쾌적한 응답시간과 데스크톱 성능 제공 목적으로 입출력중심 프로세스에 관대함 => 빠른 프로세스 응답시간
리눅스는 독창적 방식으로 이 작업 구현하여 프로세서 중심 프로세스 소홀히 하지 않음

프로세스 우선순위

스케줄링 알고리즘 일반적 형태 : 우선순위 기반 스케줄링 = 가치와 필요에 따라 프로세스의 순위 매겨 프로세스 시간 할당
일반적으로 우선순위 높은 프로세스 낮은 것보다 먼저 실행, 같은 경우 순환방식round-robin

일부 시스템은 우선순위 높은 프로세스 타임슬라이스 길게 함

시스템은 물론 사용자도 프로세스 우선순위 조작 가능

리눅스 커널은 두 가지 별개의 우선순위 단위 가짐

1. 나이스nice 값 : -20 ~ +19 사이의 값 가짐, 기본값 0

   • 클수록 우선순위 낮음(더 친절nice해짐)
   • 낮은 값 프로세스가 높은 것보다 프로세서 사용 시간 더 많이 할당받음
   • 유닉스 시스템 우선순위 표기 형식이지만 활용은 알고리즘마다 다르게 함(e.g. Mac OS X 등 유닉스 기반 OS는 nice 값으로 타임슬라이스 절대값 조절, 리눅스는 타임슬라이스 비율 조절, $ps -el로 시스템 ps목록과 각각의 나이스 값(NI 항목) 확인 가능)

2. 실시간 우선순위 : 0 ~ 99 사이의 값, 설정으로 범위 조절 가능

   • 클수록 우선순위 높음
   • 모든 실시간 프로세스가 일반적 프로세스보다 높은값 가짐
   • 나이스 값과 별도의 값
   • 유닉스 표준 POSIX.1b에 따라 구현
   • $ps -eo state,uid,pid,ppid,rtprio,time,comm.의 rtprio항목으로 실시간 우선순위 확인 가능 ('-' 표시된 경우 실시간 프로세스 아님)

타임슬라이스

타임슬라이스 너무 길면 시스템 대화형 성능 저하
너무 짧으면 프로세스 전환 오버헤드 커짐(프로세서중심인 경우 불리함)
입출력중심인지 프로세서중심인지 고려해야 함

많은 OS에서 기본 타임슬라이스 10ms로 설정

리눅스 CFS 스케줄러 프로세스별로 프로세서 할당 비율 지정
리눅스 프로세스 시간은 시스템 부하에 따른 함수로 결정됨
이 할당값은 나이스 값에 영향 받음
나이스 값은 가중치로 비율에 영향을 줌

리눅스는 새 프로세스가 현재 실행 중인 프로세스보다 낮은 비율의 프로세서 시간 사용 시 선점하고 즉시 실행됨
그렇지 않으면 나중에 실행

스케줄러 정책의 동작

대화형 작업에 많은 비율의 가용 프로세서 할당 : 프로세서 많이 필요하지 않지만 필요한 순간에 항상 프로세서 시간 얻기 위함, 깨어나는 순간 프로세서중심 프로세스 실행하는 프로세서 선점해야 함
=> 이렇게 해야 좋은 대화형 성능 보장 가능

많은 OS는 대화형 작업에 높은 우선순위, 긴 타임슬라이스 할당해 해결
발전된 OS는 대화형 작업인지 자동 탐지하여 이 과정 수행
리눅스는 다른 방법 사용

리눅스는 대화형 작업에 특정 우선순위, 타임슬라이스 할당하지 않고,
일정 비율의 프로세서 시간 보장함

같은 나이스 값 가진 프로세스가 대화형 작업 A, 프로세서중심 작업 B 둘뿐이라면 이 비율은 50%임
각 프로세스는 절반의 프로세서 시간 보장받음
자연스럽게 대화형 작업이 입출력 기다리며 사용 시간 덜 사용하여 비율 커짐 대화형 작업이 깨어났을 때, CFS가 비율 차이를 알게 되고 A가 선점할 수 있게함 A가 다시 입출력 대기 상태로 들어가면 B가 실행됨

리눅스 스케줄링 알고리즘

스케줄러 클래스

리눅스 스케줄러는 모듈화되어 있음
여러 유형의 프로세스를 각기 다른 알고리즘 적용 스케줄링 가능

스케줄러 클래스 이용 교체 가능한 여러 알고리즘 동시 사용하며 클래스별로 독자적 방식 프로세스 스케줄링 가능

각 스케줄러 클래스에 우선순위 존재
kernel/sched.c에 정의된 기본 스케줄러 코드는 각 스케줄러 클래스를 우선순위에 따라 차례대로 실행함
실행 가능한 프로세스가 있는 가장 우선순위 높은 스케줄러가 다음에 실행할 프로세스 선택함

CFS는 SCHED_NORMAL로 정의된(POSIX 표준에서는 SCHED_OTHER) 리눅스의 일반 프로세스용 스케줄러 클래스 CFS는 kernel/sched_fair.c에 정의됨

유닉스 시스템의 프로세스 스케줄링

현대 프로세스 스케줄러의 두 가지 공통 개념 : 프로세스 우선순위, 타임슬라이스

유닉스에서 우선순위 : 나이스 값 형태로 사용자 공간에 개방됨
=> 방법론적인 문제 존재

1. 나이스 값과 타임슬라이스 연계시키려면 각 나이스 값에 할당할 타임슬라이스 절대값 정해야 함

   • 작업 전환이 최적화 잘 안됨 : 같은 우선순위 두 개 프로세스만 존재 시 두 프로세스의 우선순위가 높은 경우는 오래, 낮은 경우는 짧게 실행됨
     하지만 높은 우선순위인 경우 포어그라운드 사용자 작업, 낮은 우선순위 경우 백그라운드 프로세서중심 작업일 가능성 커서 비이상적

2. 나이스 값 1 차이가 5ms의 타임슬라이스 차이를 만듬

   • 10ms와 5ms간의 차이와 100ms와 95ms간의 차이의 간극 존재

3. 대부분 OS에서 타이머 클럭의 일정 배수로 타임슬라이스 단위 정해야 함

   • 타이머 틱이 10ms일수도 1ms일수도 있으므로, 타이머 틱보다 타임슬라이스 작아질 수 없고, 시스템 타이머에 타임슬라이스 차이가 의존적이게 됨

4. 깨어난 즉시 해당 작업 실행될 수 있도록 타임슬라이스 소진한 경우에도 해당 프로세스 우선순위 끌어올려 주고 싶은 경우 존재

   • 한 프로세스가 나머지를 희생시키게 되는 불공정한 상황 만드는 방법론적 허점 야기함

나이스 값에 따른 타임슬라이스 값을 선형이 아닌 기하적인 값 사용 시 2번째 문제 해결 가능

나이스 값에 할당하는 타임슬라이스 단위를 타이머 틱에 영향 받지 않도록 정하여 3번째 문제 해결 가능

하지만 타임슬라이스 값을 지정하는 고정된 전환 비율 사용 시 궁극적 해결책이 될 수 없음

CFS는 작업 전환 비율 조정(타임슬라이스 값 무시하고 각 프로세스에 할당할 프로세서 비율 정함)을 통해 일정한 공정성 유지

공정 스케줄링

단순한 개념 바탕
이상적이고 완벽한 멀티태스킹 프로세서 가진 시스템의 프로세스 스케줄링 추구

실행 가능한 프로세스 n개 시,
이상적 시스템 각 프로세스에 1/n의 프로세서 시간 할당,
이런 프로세스를 무한히 작은 시간 단위로 스케줄링하여 특정 시간 안에 n개 프로세스 모두 동일 시간 동안 실행되게 할 수 있음

표준 유닉스 방식에선 한 프로세스 5ms 실행 후 다른 것 5ms 실행(실행중인 프로세스가 프로세서 100% 사용하며) 이상적 완벽한 멀티태스킹 프로세서라면 10ms 동안 프로세서 50%씩 사용하는 두 프로세스 동시 실행 가능 <= 완전 멀티태스킹이라고 함

하지만 한 프로세서에서 여러 개 프로세스 동시 실행 불가능하므로 비현실적인 방식임
프로세스 전환 비용 때문에 극단적 짧은 시간 간격 실행은 비효율적

CFS는 각 프로세스 순차적으로 일정 시간 동안 실행하고, 가장 실행 덜 된 프로세스를 다음에 실행할 프로세스로 선택
CFS는 프로세스별로 타임슬라이스 할당하기보다 실행 가능한 전체 프로세스 개수와 관련된 함수 이용 프로세스 실행 시간 계산
CFS는 나이스 값 대신 프로세스에 할당할 프로세서 시간 비율의 가중치로 나이스 값을 사용함
우선순위 낮고 나이스 값 높을수록 프로세스는 낮은 가중치를 받고, 우선순위 높고 나이스 값 낮을수록 높은 비율 가중치 받음

각 프로세스 실행 시간 = (자신의 가중치)/(실행 가능한 전체 프로세스 가중치 총합) 비율 해당하는 크기만큼의 타임슬라이스 동안

CFS는 실제 타임슬라이스 값 계산 위해 완전 멀티태스킹의 무한히 작은 스케줄링 단위를 근사할 수 있는 목표치 정해 놓음
이 목표치(전체 프로세스에 대한 시간)를 목표 응답시간이라고 함
목표치가 작을수록 대화형 성능 좋아지고 완전 멀티태스킹에 가까워짐
하지만 전환비용 커지기 때문에 전체 시스템 효율 나빠짐

CFS는 타임슬라이스 최소 한계 가짐 = 최소 세밀도minimum granularity <= 기본값 1ms
비율이 최소 세밀도보다 낮아지면 완벽히 공정하게 작동 못함, 개선 방법 존재하긴 함

CFS는 나이스 값의 절대적 크기가 아닌 상대적 차이가 시간 할당 비율에 영향 줌

리눅스 스케줄링 구현

CFS 실제 구현은 kernel/sched_fair.c에 있음

CFS의 네가지 구성요소 - 시간 기록 - 프로세스 선택 - 스케줄러 진입 위치 - 휴면 및 깨어남

시간 기록

모든 프로세스 스케줄러는 각 프로세스 실행시간 기록해야 함
대부분 유닉스 시프템은 프로세스에 타임슬라이스 할당하며 기록함

스케줄러 단위 구조체

CFS에는 타임슬라이스 개념 없지만 실행시간 기록해 두어야 함
<linux/sched.h>에 정의된 struct sched_entity라는 스케줄러 단위 구조체 사용해 관련 정보 저장

struct sched_entity {
	struct load_weight	load;
	struct rb_node		run_node;
	struct list_head 	group_node;
	unsigned int 		on_rq;
	u64			exec_start;
	u64			sum_exec_runtime;
	u64			vruntime;
	u64			prev_sum_exec_runtime;
	u64			last_wakeup;
	u64			avg_overlap;
	u64			nr_migrations;
	u64			start_runtime;
	u64			avg_wakeup;
 // CONFIG_SCHEDSTATS 값 설정 시 사용하는 통계용 변수 생략됨
};

스케줄러 단위 구조체는 프로세스 서술자인 struct task_struct 구조체에 se 항목으로 들어 있음

가상 실행시간

vruntime 변수에는 프로세스의 가상 실행시간 저장됨